前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Think

題目給了一個n(介於1-8)，每個n代表一組()，要找出這些()*n個可以組出的合理組合，也就是每一個(一定要有)去對應

• 一開一關~

寫到有點卡住，看了一下Neetcode上的影片圖解部分，主要有兩個判斷條件：

1. "("的數量 < n，表示目前還可以繼續放(，Code中open_p代表的是"("的數量。
2. ")"的數量 < "("的數量，表示目前有(存在，所以可以放)配成一對Code中close_p代表的是")"的數量。。
3. 最後是停止條件的部分，如果找出的組合數量等於n * 2的話，就結束了~

• 後來看Neetcode上的解法，一開始以為是我複製過來排版排錯，def中又有def，查了才知道這個叫Nested Function or Inner Function。
  • Nested Functions in Python
  • 看起來是為了避免資料有可能被外部存取，透過inner fucntion，可以讓原來的功能照樣運作，但從外部function無法呼叫inner function，以達到data hiding & data privacy~
  • 還有看到一個名詞叫Closures，不太確定中文翻什麼
• Closures例子:

def num1(x):
  def num2(y):
    return x + y
  return num2
print(num1(10)(5))

These are the conditions you need to create a closure in Python:

1. There must be a nested function
2. The inner function has to refer to a value that is defined in the enclosing scope
3. The enclosing function has to return the nested function

• Source: https://stackabuse.com/python-nested-functions/

Code

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        self.backtrack(result, "", 0, 0, n)
        return result
    
    def backtrack(self, output_list: List[str], current_str: str, open_p: int, close_p: int, n: int) -> None:
        if len(current_str) == n * 2:
            output_list.append(current_str)
            return
        
        if open_p < n:
            self.backtrack(output_list, current_str + "(", open_p + 1, close_p, n)
        if close_p < open_p:
            self.backtrack(output_list, current_str + ")", open_p, close_p + 1, n)

• Neetcode上的解法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        stack = []
        res = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                res.append("".join(stack))
                return

            if openN < n:
                stack.append("(")
                backtrack(openN + 1, closedN)
                stack.pop()
            if closedN < openN:
                stack.append(")")
                backtrack(openN, closedN + 1)
                stack.pop()

        backtrack(0, 0)
        return res

Submission

今天就到這邊啦~
大家明天見